package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.*;

/**
 * https://leetcode.cn/problems/word-break/description/?envType=study-plan-v2&envId=top-100-liked
 * <p>
 * 最多通过 41/47
 * 最后参考通过
 *
 * @author yulongtian
 * @create 2024-07-22 19:58
 */
public class Test82 {
    public static void main(String[] args) {

        List<String> wordDict = new ArrayList<>();
        wordDict.add("goals");
        wordDict.add("go");
        wordDict.add("goal");
        wordDict.add("special");
        String s = "goalspecial";
        System.out.println(new Test82().wordBreak(s, wordDict));
    }

//    public boolean wordBreak(String s, List<String> wordDict) {
//        boolean res = true;
//        for (int i = 0; i < s.length(); i++) {
//            boolean tempFlag = false;
//            for (int j = i + 1; j <= s.length(); j++) {
//                String substring = s.substring(i, j);
//                if (wordDict.contains(substring)) {
//                    tempFlag = true;
//                    i = j - 1;
//                    j = s.length() + 1;
//                }
//            }
//            String substring = s.substring(i + 1);
//            if (wordDict.contains(substring)) {
//                return res;
//            }
//            res = res && tempFlag;
//        }
//        return res;
//    }

    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for (int i = 1; i <= len; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (dp[i]) {
                    break;
                }
                if (!dp[j]) {
                    continue;
                }
                String substring = s.substring(j, i);
                if (set.contains(substring) && dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }

}
